home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor2 / bogosort.doc < prev    next >
Text File  |  1995-03-31  |  3KB  |  61 lines
  1. (Comp.sys.hp48) 
  2. Item: 595 by akcs.joehorn@hpcvbbs.cv.hp.com 
  3. Author: [Joseph K. Horn] 
  4.   Subj: Bogo-Sort 
  5.   Keyw: bogosort bogus stupid blond sort algorithm 
  6.   Date: Sat Feb 08 1992 
  7.  
  8. ** PROGRAMMER'S RECREATION DEPARTMENT ** 
  9.  
  10. According to The Jargon File: 
  11.  
  12.    BOGO-SORT: n. (var. `stupid-sort') The archetypical perversely 
  13.    awful algorithm (as opposed to {bubble sort}, which is merely the 
  14.    generic *bad* algorithm). Bogo-sort is equivalent to throwing a 
  15.    deck of cards in the air, picking them up, then testing whether 
  16.    they are in order. If not, repeat. Used as a sort of canonical 
  17.    example of awfulness. Usage: when one is looking at a program and 
  18.    sees a dumb algorithm, one might say, "Oh, I see, this program uses 
  19.    bogo-sort."  Compare {bogus}. 
  20.  
  21. So, here it is. 
  22.  
  23. INPUT: List of real numbers to be sorted (with 2 or more elements). 
  24. OUTPUT: Bogo-sorted list (eventually...). 
  25.  
  26. %%HP: T(3); 
  27. @ BOGOSORT, aka STUPID-SORT and BLOND-SORT 
  28. \<< 1 CF 
  29.   DO OBJ\-> { } SWAP 1                  @ shuffle the list 
  30.     FOR j RAND j * CEIL 1 + ROLL + -1 
  31.     STEP 
  32.   UNTIL DUP OBJ\-> 2 SWAP               @ until it's in order 
  33.     START OVER < { 1 SF } IFT 
  34.     NEXT DROP 1 FC?C 
  35.   END 
  36. \>> 
  37.  
  38. The otherwise thorough "Art of Computer Programming: Sorting and 
  39. Searching" by Donald Knuth is deafeningly silent regarding the 
  40. bogo-sort algorithm.  Bob Wilson of Wichita, Kansas, says that it 
  41. would take n! iterations on the average; empirical evidence agrees. 
  42. But Harry Bertucelli says it's an exponential function of n.  Hmm. 
  43. Not that it matter much.  Very low I.Q.'s (like very high I.Q.'s) 
  44. are very hard to measure precisely... 
  45.  
  46. In any case, Kevin Jessup points out that this ought to be rewritten 
  47. in machine language because "We all know that algorithm efficiency is 
  48. not important at the assembly level."  ;-) 
  49.  
  50. BTW, the astute codophile (that's a lover of code, not of cod) will 
  51. have already noticed (unlike the rest of you lugs to whom it must now 
  52. be pointed out) that the program above first shuffles the list, then 
  53. tests its ordinality (sortedness?).  He xor she may object that it 
  54. would certainly be better to test first, thereby catching the case of 
  55. pre-sorted lists.  Ah, but that would be blemishing the face of this 
  56. blissfully idiotic algorithm with a hint of intelligence.  And 
  57. algorithms, like friends, are the most fun when they're really smart 
  58. or really stupid. 
  59.  
  60. -jkh-   EQU   akcs.joehorn@hpcvbbs.cv.hp.com 
  61.